﻿namespace LeetCodeProject._0001_1000._001_100._31_40._031;

public class Solution
{
    public void NextPermutation(int[] nums)
    {
        if (nums == null || nums.Length <= 1)
            return;
        var i = nums.Length - 1;
        while (i > 0 && nums[i - 1] >= nums[i]) i--;
        if (i == 0)
        {
            Reverse(nums, 0, nums.Length - 1);
            return;
        }

        Reverse(nums, i, nums.Length - 1);
        var idx = Array.BinarySearch(nums, i, nums.Length - i, nums[i - 1] + 1);
        if (idx < 0)
            idx = ~idx;
        Swap(nums, i - 1, idx);
        Array.Sort(nums, i, nums.Length - i);
    }

    private void Reverse(int[] arr, int i, int j)
    {
        while (i < j)
        {
            Swap(arr, i++, j--);
        }
    }

    private void Swap(int[] arr, int i, int j)
    {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}